The present invention relates to a device for, and method of, implementing a Multiple Random Access Memory (RAM)-Based Content Addressable Memory (CAM), and more particularly, a Multiple RAM-Based Binary CAM and a Multiple RAM-Based Range Content Addressable Memory (RCAM).
Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their respective addresses.
Content Addressable Memories (CAMs) are associative memories that contain key entries and associated data entries that uniquely correspond to the key entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the associated data for any key that is submitted to be searched in the CAM.
A binary CAM stores an ordered list of single integer key entries and a corresponding list of their associated data. An RCAM stores instead a list of key entries that represent range boundaries and a list of associated data that correspond uniquely to these ranges. A key search in a binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.
A successful approach to utilizing RAM-based technology on a binary CAM is provided in a co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns. Each of the key entries in these cells has a unique pair of indices that indicate the key entry location in the array. The associated data entries corresponding to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array and a match signal, “True” or “False”, is output along with the retrieved associated data entry to indicate whether the associated data is valid or not. The key entries in the two-dimensional array are arranged in monotonic order. The entries are arranged in the array so that at least a portion of the array is filled with valid entries, without blanks. The arrays of the key entries and their associated data are kept in perfect sequence by Insert and Remove algorithms.
The main innovations introduced by this technology include:                Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in significant savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.        Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. Although, in theory, single clock latency may be accomplished, pipelining may yield a better throughput and a similar latency if measured on an absolute time scale (nano-seconds).        Continuous “Housekeeping” Procedure: Unlike CAMs of the prior art, these CAM devices keep the “house in order”. That is, the deletion of keys does not leave “holes” in the list, which would otherwise require “housekeeping” operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This “housekeeping” procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.        
In U.S. Pat. No. 6,633,953, which is incorporated by reference for all purposes as if fully set forth herein, a method and apparatus are disclosed for arranging and storing a set of key entries and a corresponding set of associated data entries in storage areas within a memory device. Each location in the first storage area is assigned a unique index and is associated with the corresponding location to second storage area with the same index. Each key entry represents a range of consecutive values and is denoted herein as Range Key Entry. The range may be represented by its lower or upper boundary.
When a key is submitted for search and is found to belong to a range represented by a range key entry, the associated data entry with the same index is extracted from the memory as valid data and a Match signal is issued. If no range is found to contain the submitted key, no valid associated data is retrieved and a No-Match signal is issued.
In a co-pending, unpublished PCT Patent Application Serial No. IL01/01025, which is incorporated by reference for all purposes as if fully set forth herein, RAM-based technology is implemented on an RCAM in a somewhat analogous fashion to the above-described implementation of RAM-based technology on a binary CAM. A method and apparatus are disclosed therein for the high-rate arrangement, storage of ranges of integers, and extraction of data associated with these ranges in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries (representing range boundaries) in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond uniquely to these ranges are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found within an integer range, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array.
The RCAM optionally includes a third two-dimensional array, consisting of associated boundary type entries that also correspond uniquely to these ranges and are stored under the same pair of indices. These entries determine the validity of the corresponding ranges. A match signal, “True” or “False”, is output accordingly with the retrieved associated data entry to indicate whether the matched range and the associated data are valid or not. The array of associated boundary type entries can be stored in conjunction with that of associated data entries or separately.
The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries.
In U.S. Pat. No. 6,633,953, which is incorporated by reference for all purposes as if fully set forth herein, a method and device are disclosed for the interconnection of multiple Binary CAM or RCAM modules into a single Binary CAM or RCAM device. The invention allows the division of the Binary CAM or RCAM structure into partial modules, each containing a small number of rows. The use of the smaller partial modules significantly speeds up the Insert and Remove operations in these devices because the Insert and Remove throughputs are inversely proportional to the number of rows in the CAM or RCAM.
Each module of a Multiple-Module Binary CAM or RCAM operates internally like a single Binary CAM or RCAM, with a Key Module List, Associated Data List and Associated Boundary Type List (for the RCAM). Each of these lists is stored in a Two-Dimensional Array (TDA) using RAM-based technology. A search of the submitted key is performed concurrently in all the modules of the Binary CAM or RCAM. The Data and Match signals correspond to those of the individual module that contains the searched key; they are obtained by summing-up the results of the Search operation performed in all the modules.
However, since each module of a Multiple-Module Binary CAM or RCAM requires several registers, such as First Column Register, Inserter/Remover Register and others, plus additional components, the integrated device may become large if it includes many modules.
It would, therefore, be highly desirable and of distinct advantage to have a Multiple-RAM device for, and a method of significantly improving the efficiency in the storage and key search operations of devices utilizing multiple RAMs.